package 矩形覆盖;
//题目描述
//我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，
// 总共有多少种方法？
//
//比如n=3时，2*3的矩形块有3种覆盖方法
public class Solution
{
    public int RectCover(int target)
    {
        //数学问题
        //判断输入
//        if (target==0)
//            return 0;
//        int cnt=target/2;
//        if (target%2==0)
//        {
//            return (int)Math.pow(2,cnt);
//        }
//        else
//        {
//            return (int)((cnt+1)*Math.pow(2,cnt));
//        }
        //有特殊情况，导致不行，单的那一个会和双的组合到一起成为一种情况
        //还是裴波那契数列问题
        if (target==0)
            return 0;
        if (target==1)
            return 1;
        if (target==2)
            return 2;
//        return RectCover(target-1)+RectCover(target-2);//递归耗时长
        //递推法
        int minus1=2;
        int minus2=1;
        int res=0;
        for (int i = 3; i <= target; i++)
        {
            res=minus1+minus2;
            minus2=minus1;
            minus1=res;
        }
        return res;

    }
}
